﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.ComponentModel.Composition;
using System.Runtime.Serialization;

using NuMetaheuristics.Utility;

namespace NuMetaheuristics.Algorithms
{
    /// <summary>
    /// The basic genetic algorithm imposes a generational cycle on its
    /// population, producing a new population from the existing one after
    /// every cycle, using crossover and mutation.
    /// </summary>
    /// <remarks>
    /// For each generation cycle, pairs of candidate solutions are selected 
    /// to produce children by crossover and then mutation, contributing to a
    /// new population. When enough children have been bred, the new 
    /// population replaces the current one. 
    /// 
    /// One of the key parts in this algorithm is the selection method. A 
    /// tournament selection is used, using the given tournament size.
    /// </remarks>
    /// <typeparam name="G">The genotype class which inherits from IGenotype.</typeparam>
    [DataContract(Name = "GeneticAlgorithmOf{0}",
        Namespace = "http://numetaheuristics.codeplex.com/schemas")]
    [Export(typeof(IAlgorithm<>))]
    public class GeneticAlgorithm<G> : IAlgorithm<G>, IDeserializationCallback
        where G : IGenotype
    {
        /// <summary>
        /// Produces offspring from the given parents.
        /// </summary>
        [DataMember]
        private IBinaryOperator<G> _crossover;

        /// <summary>
        /// Mutates offspring before they are added to the new population.
        /// </summary>
        [DataMember]
        private IUnaryOperator<G> _mutator { get; set; }

        /// <summary>
        /// Determines the size of the tournament used in selecting parents 
        /// from the population.
        /// </summary>
        [DataMember]
        private int _tournamentSize { get; set; }

        private RandomNumberGenerator _rng;

        /// <summary>
        /// The default, no-argument constructor.
        /// </summary>
        public GeneticAlgorithm()
        {
            _rng = new RandomNumberGenerator();
        }

        /// <summary>
        /// The complete constructor which initializes all properties.
        /// </summary>
        /// <param name="tournamentSize">The size of tournament to use for the 
        /// breeding selection process.</param>
        /// <param name="crossover">The operater used to produce offspring.</param>
        /// <param name="mutator">The operator used to tweak offspring.</param>
        public GeneticAlgorithm(int tournamentSize, IBinaryOperator<G> crossover, IUnaryOperator<G> mutator)
        {
            _tournamentSize = tournamentSize;
            _crossover = crossover;
            _mutator = mutator;

            _rng = new RandomNumberGenerator();
        }

        /// <summary>
        /// Run the algorithm against the given population, using the given 
        /// context, for a given number of iterations. Assumes the population 
        /// has already been evaluated and sorted.
        /// </summary>
        /// <param name="population">The population of candidate solutions to 
        /// operate on.</param>
        /// <param name="context">The context, containing all of the tools 
        /// necessary to work within the desired problem space</param>
        /// <param name="iterations">The number of iterations to run the 
        /// algorithm for.</param>
        public void Run(Population<G> population, IContext<G> context, uint iterations)
        {
            for (uint i = 0; i < iterations; i++)
            {
                //create a list of parents
                List<Tuple<G, G>> parents = new List<Tuple<G, G>>();
                for (uint j = 0; j < (population.Genomes.Count() / 2); j++)
                {
                    G a = tournamentSelect(population.Genomes);
                    G b = tournamentSelect(population.Genomes);

                    parents.Add(new Tuple<G, G>(a, b));
                }

                List<G> children = new List<G>();
                foreach (Tuple<G,G> couple in parents)
                {
                    G child1 = _crossover.Operate(couple.Item1, couple.Item2);
                    G child2 = _crossover.Operate(couple.Item1, couple.Item2);

                    _mutator.Operate(ref child1);
                    _mutator.Operate(ref child2);

                    context.MakeValid(ref child1);
                    context.MakeValid(ref child2);

                    children.Add(child1);
                    children.Add(child2);
                }

                population.Genomes = children;

                foreach (G genome in population.Genomes)
                {
                    var g = genome;
                    context.Evaluate(ref g);
                }
                population.Genomes.Sort();
            }
        }

        public void OnDeserialization(object sender)
        {
            _rng = new RandomNumberGenerator();
        }

        private G tournamentSelect(List<G> genomes)
        {
            int a = _rng.Next(0, genomes.Count());

            for (int i = 1; i < _tournamentSize; i++)
            {
                int b = _rng.Next(0, genomes.Count());

                if (genomes[b].Fitness > genomes[a].Fitness)
                {
                    b = a;
                }
            }

            return genomes[a];
        }
    }
}
